home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The 640 MEG Shareware Studio 2
/
The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO
/
os2
/
pccts.zip
/
UPDATE10.TXT
< prev
Wrap
Text File
|
1992-12-08
|
35KB
|
1,117 lines
The Purdue Compiler Construction Tool Set
Version 1.06 Update
December 1, 1992
1. Enhancements
This section describes the update of PCCTS Version 1.00 to Ver-
sion 1.06 (1.01-1.05 were internal releases). The list of changes
here is not complete since many "little" fixes were made (actually,
the predicated parsing feature is major). Here, we concentrate on the
enhancements to the system; file BUGS100 contains a list of the bug
fixes incorporated in the 1.06 release. In addition, note that the
manual has not been updated and will not be until the next major
release (or until we get around to it).
1.1. Predicated Parsing - ALPHA Version
Normally, parsing is a function of syntax alone. Semantics
(meaning/value of the input) are not taken into account when parsing
decisions are made-context-free parsing. Typically, languages, such
as C++, have some rules which require the lexical analyzer to consult
the symbol table to determine what token (e.g. classname verses
enumerated name verses typedef name) is given to the parser. However,
lexical analyzers have no context information except the current token
of lookahead and must be coerced via flags to yield the various token
types. Ad hoc approaches become increasingly difficult to implement
as the number of ambiguities (due to lack of semantic information) in
a grammar rises.
Context dictates the scope of variables in programming languages.
Because only the parser has context information, it is reasonable to
assume that the parser is the correct place to maintain and access the
symbol table; there are other situtations in which it is useful to
have context direct parsing. Unfortunately, most parser generators do
not allow grammar actions to influence the parse; i.e. parsing is a
function of syntax alone. Because PCCTS generates recursive-descent
LL(k) parsers in C, allowing user-defined C actions to influence pars-
ing is a straightforward and natural addition to the PCCTS description
meta-language. Although bottom-up parsing strategies can allow
actions to direct parsing, bottom-up parser have much less semantic
information; i.e. LR and LALR techniques allow only S-attributed gram-
mars whereas LL allows L-attributed grammars (for example, LL always
knows which set of rules it is currently trying to match whereas LALR
does not, in general; see your favorite book on parsing theory).
In this section, we introduce a rudimentary version of predi-
cates, with a full implementation to appear in future releases. To
support context-sensitive parsing PCCTS 1.06 allows a new action type
called predicate (-pr must be used), which is denoted:
Page 1
PCCTS
<<predicate>>?
or, optionally,
<<predicate>>?[fail_action]
where the second notation "passes" an argument of an action to the
predicate operator "?", which is executed upon predicate failure. A
predicate is a C action that evaluates to either true (success) or
false (failure) and can be used for both semantic validation and for
disambiguating syntactic conflicts in the underlying grammar.
Validation predicates are used as simple tests and are function-
ally equivalent to the following normal action:
if ( !predicate ) {error message; exit rule}
or, when a fail action is present:
if ( !predicate ) {fail_action}
For example,
a : A <<pred>>? B
;
Matches A, evaluates pred, and matches B if pred is true else an error
is reported (i.e. "failed predicate 'pred'") and rule a is exited
before matching B. To generate a more useful error message, the user
may specify a fail action:
a : A <<pred>>?[fail] B
;
which executes fail when pred evaluates to false.
A predicate which validates a production can, at the same time,
be used to disambiguate a syntactically ambiguous grammar structure.
To be a candidate, a predicate must appear on the extreme left edge of
a production. Disambiguating predicates are used in the alternative
prediction expressions to enable or disable certain alternative pro-
ductions of a block (rule or subrule). Parsing in this new
Page 2
PCCTS
environment can be viewed in this way:
step 1: Disable invalid productions
An invalid production is a production whose disambiguating predi-
cate evaluates to false.
step 2: Parse as normal block
Once a list of valid productions has been found, they are parsed
as a normal rule or subrule.
Essentially, disambiguating predicates "gate" alternative productions
in and out depending on their "applicability". Productions without
predicates have an implied predicate of <<TRUE>>?; i.e. they are
always valid.
A single predicate can be used as both a validation and a disam-
biguating predicate-ANTLR determines which way to use them automati-
cally. The role taken by a predicate depends on its location in the
grammar. Predicates are all considered validation predicates as they
must always evaluate to true for parsing of the enclosing production
to continue. However, when a grammatical ambiguity is discovered,
ANTLR searches for visible predicates to disambiguate the construct.
A visible predicate is one which can be evaluated in a production
prediction expression without consuming a token or executing an action
(except initialization actions); e.g. all disambiguating predicates
appear on the left edge of some production. Fail actions are not used
in prediction expressions because a failed predicate disables a pro-
duction; it does not report a syntax error unless no other viable
predicates are present; a viable production is one which is predicted
by the lookahead. The action of moving a predicate into a prediction
expression is called hoisting; currently, at most one predicate can be
hoisted per ambiguous production. In general, predicates may only be
a function of:
User variables
This is dangerous as hoisting may evaluate the predicate in a
scope where the variable(s) does not exist; e.g. using rule
parameters can be a problem if a predicate that references them
is hoisted outside of the rule.
Attributes
Only attributes in the left context can be used; i.e. attributes
of rules/tokens created before the predicate is evaluated.
Lookahead
The next k tokens of lookahead can be tested via LA(i),
LATEXT(i).
Also, predicates may not have side-effects (user must undo anything
that was changed if they do; in other words, they must "backtrack").
See the Future Work section for information regarding the use of
predicates and extremely large lookahead buffers.
Consider the following simple grammar:
Page 3
PCCTS
a : <<pred1>>? A B
| <<pred2>>? A C
;
This grammar is LL(2) (-k 2) and ANTLR would not report an ambiguity.
However, it is LL(1) ambiguous (-k 1) and antlr t.g would generate a
warning message:
t.g, line 1: warning: alts 1 and 2 of rule ambiguous upon { A }
Now, if we allow predicates to be used with antlr -pr t.g, then ANTLR
finds that both predicates are visible and can be used to disambiguate
the production; it is up to the user to ensure that the predicates do,
in fact, disambiguate the predicate. ANTLR would generate code simi-
lar to the following:
a()
{
if ( pred1 && LA(1)==A ) {
}
else if ( pred2 && LA(1)==A ) {
}
else error;
}
The following grammars are syntactically and semantically equivalent
to the above grammar, but the predicates are not hoisted trivially:
a : ( <<pred1>>? A B )
| <<pred2>>? A C
;
ANTLR looks inside the subrule of production one and finds that pred1
can be evaluated before executing an action and before matching a
token; it is hoisted for use in the prediction expression of rule a.
Predicates can be hoisted from other rules as well:
Page 4
PCCTS
a : b
| c
;
b : <<pred1>>? A B
;
c : <<pred2>>? A C
;
Rule a would still have the same production prediction expression.
The following grammar does not have predicates that can be hoisted to
disambiguate the prediction:
a : A <<pred1>>? B /* cannot hoist past token */
| <<action>> <<pred2>>? A C /* cannot hoist past action */
;
Now, consider how a simplified version of K&R C variable and
function declarations could be specified:
decl: /* variable definition, function DECLARATION/DEFINITION */
type declarator ( func_body | ";" )
| /* function DEFINITION */
declarator func_body
;
type: "int"
| "float"
| WORD
;
declarator
: WORD { "\(" args "\)" }
;
func_body
: ( decl )* "\{" (decl)* (stat)* "\}"
;
unfortunately, rule decl is totally ambiguous in the LL(1) sense (and
in the LL(k) sense) since WORD can begin both alternatives of rule
decl. Increasing the lookahead to two tokens does not help as the
alternatives are ambiguous upon WORDWORD. Alternative one could match
my_type var and alternative two could match func my_type; hence, the
second alternative matches at least one invalid sentence. This is
because the ( decl )* subrule of rule func_body, which would match the
second WORD of WORD WORD, does not know if an argument list was seen
Page 5
PCCTS
previously or not. The question of whether to match a parameter
definition list after a declarator is context-sensitive because a
function header may or may not have been seen immediately beforehand.
One way in which this subset could be recognized is to recognize
a large superset of the language and then, using actions, verify that
the input was valid:
decl: {type} declarator ( func_body | ";" )
;
But, jamming everything together makes action introduction more com-
plicated. It is better to specify the input language exactly with
predicates.
To overcome the ambiguity in rule decl and to ensure that only a
function declarator is followed by a parameter definition, we augment
the grammar as follows:
decl: <<int is_func;>>
/* variable definition, function DECLARATION/DEFINITION */
type declarator > [is_func]
( <<is_func>>?[printf("warning: declarator not func\n");]
func_body
| ";"
)
| /* function DEFINITION */
declarator > [is_func]
<<is_func>>?[printf("warning: expecting func header not %s\n", LATEXT(1));]
func_body
;
type: "int"
| "float"
| <<LA(1)==WORD ? isTYPE(LATEXT(1)) : 1>>?
WORD
;
declarator > [int is_func]
: <<LA(1)==WORD ? !isTYPE(LATEXT(1)) : 1>>?
WORD ( "\(" <<$is_func=1;>> args "\)" | <<$is_func=0;>> )
;
func_body
: ( decl )* "\{" (decl)* (stat)* "\}"
;
In rule type, we add a predicate that ensures that, if the lookahead
Page 6
PCCTS
is a WORD, that the WORD is, in fact, a user-defined type; nothing can
be said if the lookahead is something else, so we return success in
that case; i.e. the predicate does not apply for that lookahead (con-
text). If rule declarator is called, a failure of the predicate will
report a semantic error. In our example, the predicate is also
hoisted for use as a disambiguating predicate in rule decl. The
predicate in rule declarator ensures that, if the lookahead is a WORD,
that the WORD is not a user-defined type. As before, it is also
hoisted to rule decl to disambiguate the second production of that
rule. Both productions of rule decl have predicates that are hoisted
into the prediction expressions for those productions; ANTLR assumes
that the hoisted predicates completely disambiguate the decision,
which is true in our case. The first predicate physically present in
rule decl ensures that, if a function body is coming up, the declara-
tor was a function header. The second predicate in rule decl again
ensures that a function header was seen before trying to match a func-
tion body. The variable is_func is set to the return value of rule
declarator, which is set by two simple actions in declarator.
Currently, the context under which predicates are evaluated may
not be correct; i.e. currently ANTLR does not compute the context from
which it hoists a predicate. For example,
a : b B
| (X Y | A C)
;
b : <<pred>>? A
;
The predicate pred will be hoisted for use in disambiguating rule a.
However, the predicate will be evaluate regardless of whether A, which
is its context, or X is on the input stream. It may be invalid to
apply the predicate when the lookahead is X. The user may overcome
this by changing pred thus:
a : b B
| (X Y | A C)
;
b : <<LA(1)==A ? pred : TRUE>>? A
;
which will ensure that the predicate is only evaluated when A is seen
on the input stream.
Another problem area lies in that hoisting can occur in situa-
tions that will break the semantics. For example:
Page 7
PCCTS
a : b[3]
| A
;
b[int i]
: <<f($i)>>? A
;
The predicate f(i) will be hoisted to rule a where the parameter i is
not even defined. Either do not do this or put a predicate (dummy or
otherwise) between the decision and the predicate you do not wish to
be hoisted:
a : <<1>>? b[3]
| A
;
b[int i]
: <<f($i)>>? A
;
This is an alpha release feature in that it is not anywhere near
what we want it to do and has NOT been thoroughly tested. User
beware. We do not guarantee that the syntax of predicates will stay
this way; however, the semantics will not change. We want users to
play with predicates to find new, better or different ways of doing
things. We really want user feedback on these critters before a full
implementation is developed. For example, how do you want the parser
to respond if no valid, viable production is found?
a : <<p1>>? A
| <<p2>>? A
| B
;
If the input were C, a correct error message would be reported:
line 1: syntax error at "C" missing { A B }
This is the correct message because it is truly a syntax, as opposed
to semantic, error. On the other hand, upon input A, when predicates
p1 and p2 are false, the parser reports the following bizarre message:
line 1: syntax error at "A"
Page 8
PCCTS
which is not very meaningful. The fail function, zzFAIL, found that,
in fact, A is syntactically valid and got confused because an error
was raised; this is because the fail routine has no semantic informa-
tion. A suitable definition of error reporting in the predicate
environment must be created.
Please send any suggestions/questions to parrt@ecn.purdue.edu,
hankd@ecn.purdue.edu or use the email server mechanism at
pccts@ecn.purdue.edu (send a Subject: line of "question antlr" and
fill in the body of the email with your suggestion/question).
1.2. 1.06 Is Written in 1.00
The grammar for the PCCTS meta-language (file format) has been
implemented in Version 1.00, making heavy use of #lexclass directives.
File lexhelp.c has been eliminated due to the superiority of 1.00 to
1.00B.
1.3. ANTLR Compiles Under ANSI C
Because of the rewrite of the grammar and some rewrites of ANTLR
code, ANTLR now compiles with ANSI compilers without a wimper (except
for two "unknown escape sequence" warnings). Your mileage may vary.
1.4. Grammar Files Distributed
antlr.g and dlg_p.g are now included in the source distribution
for 1.06. Note that the 1.00 PCCTS (both ANTLR and DLG) are required
to process these grammar files. DO NOT DESTROY YOUR OLD COPY OF 1.00
PCCTS (at least save the executables).
1.5. Script Generates Makefiles for PCCTS Projects
A C program called genmk.c is available in the support directory
of the PCCTS release which has the following usage:
genmk project f1.g f2.g ... fn.g
It generates a makefile that creates an executable, project, from a
set of grammar files. For example, genmk t t.g generates:
Page 9
PCCTS
#
# PCCTS makefile for: t.g
#
DLG_FILE = parser.dlg
ERR_FILE = err.c
HDR_FILE = stdpccts.h
TOK_FILE = tokens.h
K = 1
ANTLR_H = .
BIN = .
ANTLR = $(BIN)/antlr
DLG = $(BIN)/dlg
CFLAGS = -I. -I$(ANTLR_H)
AFLAGS = -fe err.c -fh stdpccts.h -fl parser.dlg -ft tokens.h -k $(K)
-gk
DFLAGS = -C2 -i
GRM = t.g
SRC = scan.c t.c err.c
OBJ = scan.o t.o err.o
t: $(OBJ) $(SRC)
cc -o t $(CFLAGS) $(OBJ)
t.c parser.dlg : t.g
$(ANTLR) $(AFLAGS) t.g
scan.c : parser.dlg
$(DLG) $(DFLAGS) parser.dlg scan.c
This program is handy when beginning a new PCCTS project or when first
learning about PCCTS.
1.6. DLG Supports Case Insensitive Scanners
DLG has two new options which provide control over the case sen-
sitivity of the generated scanner. Specifically, case insensitivity
implies that when a character is referenced in a regular expression,
DLG behaves as if the user had typed both upper and lower case ver-
sions of that character; i.e. (a|A) where a is some character. The
new options are:
-ci Make lexical analyzer case insensitive
-cs Make lexical analyzer case sensitive (default).
1.7. Delayed Lookahead Fetches in Generated Parser
Currently, PCCTS generates parsers which always have k tokens of
lookahead. This is done by following the strategy that another token
is fetched (zzCONSUME) when one is matched (zzmatch). This can be a
Page 10
PCCTS
problem for actions that need to occur after a token has been matched,
but before the next token of lookahead is fetched. This is somewhat
overcome in PCCTS 1.00 by delaying the fetch if an action is found
immediately after a token reference. With the new delayed lookahead
scheme, the next token is not consumed until the next match is
required. This means that any action before the next match (not
necessarily adjacent to the previous match) will be executed before a
lookahead fetch occurs. Turn on ANTLR option -gk and DLG option -i to
enable this feature. This feature appears to work with AST's and
attributes with the constraints mentioned below in the incompatibili-
ties section (e.g. use of LA(i) and LATEXT(i) has been restricted).
It has been tested with the C (k>1 and Pascal (k==1) examples provided
in the release and with several other large grammars.
This feature is primarily useful for developers of interactive
tools. Previously, it was really hard to get PCCTS to generate truly
interactive tools. It appeared as if the parser was always waiting on
a token fetch rather than executing an appropriate action. E.g. in
PCCTS 1.00,
a : ( "A" "B" "C" "\n" ) <<printf("got it\n");>>
;
would not print got it until one token after the newline had been
typed. PCCTS 1.06 will generate parsers that print the message
immediately upon newline and will exit without waiting for another
token as there are no token references following the action.
Another way in which delayed lookahead is useful lies in transla-
tors which add symbols to the symbol table which must be examined by a
lexical action. If a lookahead fetch occurs too fast, the lexical
action may miss the introduction of a symbol into the symbol table.
This feature is a bit flaky for the moment-LA(i) and LATEXT(i)
will generally not have the same values as when the -gk option is not
used (for k>=2). Use attributes to access token values; the lookahead
buffer is not really a user object. If you insist upon accessing the
lookahead buffer, use LA(0) and LATEXT(0), which typically access the
last token matched and last text matched respectively; this is dis-
tinguished from LA(1), which means the next token of lookahead.
Accessing the next token of lookahead is invalid because it will not
be fetched from the input stream until needed (just before the next
decision or match).
1.8. Tutorials Available
With release 1.06, we are distributing both a beginning and
advanced tutorial. They have not been thoroughly "debugged" much are
much better than nothing:
Beginning
This tutorial introduces the basic functionality of PCCTS by
Page 11
PCCTS
example. The user need not be familiar with parsing theory or
other compiler tools, but any familiarity reduces the learning
curve substantially.
Advanced
Constructing a translator can be viewed as an iterative refine-
ment process moving from language recognition to intermediate-
form transformation. This tutorial presents one possible
sequence of refinements. It uses as many features of PCCTS as is
reasonable without regards to optimality. It develops a compiler
for a simple string manipulation language called sc. The result-
ing compiler generates code for a simple stack machine.
1.9. Error Messages for k>1
Previous versions of PCCTS did not handle error message correctly
for k>1. For example, with two tokens of lookahead and the following
grammar:
a : "A" "B" "D"
| "A" "C" "E"
;
an incorrect input of A D D would yield:
line 1: syntax error at "A" missing A
which is wrong (and incredibly confusing). The new error mechanism
generates the following error message upon the same incorrect input:
line 1: syntax error at "A D"; "D" not in { B C }
which is infinitely superior. Unfortunately, situations may arise
when even this method will give an invalid message. This may occur
when alternatives have lookahead sequences which are permutations of
the same tokens.
The definition of the standard error reporting function, zzsyn()
has been modified. The parameter list is now:
Page 12
PCCTS
void
zzsyn(char *text,
int tok,
char *egroup,
unsigned *eset,
int etok,
int k,
char *bad_text);
Users can ignore this as it is transparent to them; unless, of course,
the standard error reporting must be modified. In addition, zzFAIL is
now a function rather than a macro.
1.10. Trace Facility has Exit Macro
Previously, only an entry trace macro was inserted in parsers
when the -gd ANTLR option was used. An exit macro has been defined
which resulted in zzTRACE becoming zzTRACEIN. Also, a default trace
macro prints out "enter rule rule" if no default trace macros are
defined. To define your own, the macro definitions must appear in the
#header action. As before, the sole argument to the trace routines is
a string representing the rule which has been entered or is about to
be exited.
1.11. Resource Limitation
Occasionally, ANTLR is unable to analyze a grammar submitted by
the user. This rare situation can only occur when the grammar is
large and the amount of lookahead is greater than one. A nonlinear
analysis algorithm is used by PCCTS to handle the general case of
LL(k) parsing. The average complexity of analysis, however, is near
linear due to some fancy footwork in the implementation which reduces
the number of calls to the full LL(k) algorithm.
To avoid the situation where ANTLR takes 23 hours of CPU time and
then runs out of virtual memory, use the -rl n resource limit option
where n is the maximum number of tree nodes to be used by the analysis
algorithm. An error message will be displayed, if this limit is
reached, which indicates which grammar construct was being analyzed
when ANTLR hit a non-linearity. Use this option if ANTLR seems to go
off to lunch and your disk start swapping; try n=10000 to start. Once
the offending construct has been identified, try to remove the ambi-
guity that ANTLR was trying to overcome with large lookahead analysis.
Future versions of PCCTS may incorporate a known algorithm that does
not exhibit this exponential behavior.
1.12. Rule Prefix Option
An ANTLR option has been added that prefixes all functions
corresponding to rules with a prefix. This can be used to provide
symbol hiding in your project to isolate the parser. It can also be
used to allow rule names that correspond to C keywords such as if and
Page 13
PCCTS
typedef.
1.13. Standard PCCTS Header
Two new ANTLR options have been added that control the creation
of a standard PCCTS header file - stdpccts.h. Option -gh instructs
ANTLR to create a file, stdpccts.h unless -fh is used, which contains
all header information needed by non-PCCTS generated files that want
to access PCCTS symbols. For example, it indicates the k of the
parser, whether trees are being constructed, whether lookahead is to
be delayed, and indicates what the user specified in the #header
action in the grammar file. Previously, the user had to manually con-
struct this information from the grammar file in order to place the
information in a non-PCCTS C file. The -fh option is merely used to
rename stdpccts.h.
1.14. Doubly-Linked AST's
A new function is available in ast.c which will doubly-link any
tree that is passed in. To use this option, the user must define
zzAST_DOUBLE in the #header directive or on the command-line of the C
compile. This defines left and up fields automatically in the AST
node typedef. ANTLR generated parsers, normally, only construct
singly-linked trees. The fields can be filled in via code similar to
the following:
#header <<
#define AST_FIELDS user-fields;
>>
<<
main()
{
AST *root = NULL;
ANTLR(start(&root), stdin);
zzdouble_link(root, NULL, NULL);
}
where the function is defined as:
zzdouble_link(AST *t, AST *left, AST *up);
1.15. C++ Compatible Parsers
PCCTS parsers may now be compiled with C++ compilers; i.e. the
output is more ANSI C-like than before. It has been successfully com-
piled with GCC 2.2, but not with GCC 1.37. We do not guarantee any-
thing. To be safe, use the -ga option so that PCCTS generates ANSI-
style prototypes for functions generated from rules. As a simple
Page 14
PCCTS
example, consider:
#header <<
#include "charbuf.h"
/* stdio.h is included, by default, but doesn't seem to bother stream.h */
#include <stream.h>
#include <stdlib.h>
>>
#token "[\ \t\n]" <<zzskip();>>
<<
main()
{
ANTLR(a(), stdin);
cout << "end of C++ test\n";
}
>>
a : "A" "B" << cout << $1.text << $2.text << "\n"; >>
;
which does not do much:
% t
A B
AB
end of C++ test
%
but it does compile with G++ 2.2 except that a warning is generated
concerning strncpy() not being declared before use. This is trivial
to fix, of course - by modifying the charbuf.h file. We compiled this
with:
antlr -k 2 -gk -ga t.g
Antlr parser generator Version 1.06 1989-1992
dlg -C2 -i parser.dlg scan.c
dlg Version 1.06 1989-1992
g++ -I. -I../1.06/h -g -c scan.c
g++ -I. -I../1.06/h -g -c t.c
t.c: In function `struct Attrib zzconstr_attr (int, char *)':
t.c:19: warning: implicit declaration of function `strncpy'
g++ -I. -I../1.06/h -g -c err.c
g++ -o t -I. -I../1.06/h -g scan.o t.o err.o
We anticipate a rewrite to be more C++ sometime in the future.
Page 15
PCCTS
2. Acknowledgements
We acknowledge Dan Lawrence of MDBS for the new error reporting
facility concerning greater than one token of lookahead; Dana Hoggatt,
also of MDBS, suggested the rule prefix idea (-gp option) and beta
tested 1.06. We thank Ed Harfmann of MDBS for creating the
makefile.os2 files and porting it to the PC. We acknowledge the fol-
lowing beta testers for 1.06 (alphabetically): Thomas Buehlman
(buehlman@iwf.mabp.ethz.ch), Peter Dahl (dahl@everest.ee.umn.edu),
Chris Song (dsong@ncsa.uiuc.edu), Ariel Tamches (tamches@cs.UMD.EDU).
We reference Russell Quong (quong@ecn.purdue.edu) of Purdue EE for his
work with us on defining and refining predicates. Ariel Tamches
(tamches@cs.UMD.EDU) deserves attention for hacking on the particulars
of the alpha-release predicates.
3. Machine Compatibility
PCCTS Version 1.06 has been tested on the following platforms:
Sun 3/60
Sun SPARC I, II
Encore Multimax running Umax 4.3
Sun sparcstation IPX
NeXTstation
Decstation 3100 running Ultrix 4.2
DEC 5000
Linux on 386PC
Microsoft C 6.0 on PC OS/2, DOS
CSET/2 C compiler on PC OS/2
IBM RS6000
MIPS r2000
4. Incompatibilities
Due to the bug fixes in 1.06, "new" ambiguities may appear in
your grammar. These were always there-ANTLR simply did not find them.
The analysis is more correct.
Calls to zzTRACE are no longer generated by the -gd option. Now,
zzTRACEIN, zzTRACEOUT are called at the beginning and end of func-
tions, respectively.
The way in which PCCTS translates actions has been changed;
Page 16
PCCTS
before they were parsed with a C function, now the #lexclass facility
is being used. Some differences in translation may be discovered;
e.g. a character may need to be escaped with \ whereas before the sim-
ple character was sufficient.
The user should no longer set the next token of lookahead or the
text of the next token in the lexical analyzer using LA(1) and
LATEXT(1). This is incompatible with the -gk option; hence, NLA and
NLATEXT should be used instead where the N means "next".
The -ga does not generate anything different as the code genera-
tor now dumps both K&R and ANSI with #ifdef's around the ANSI code.
Previously, no prototype was given when -ga was off. Now, proto-
types are always generated (with the appropriated #ifdef's). These
prototypes can conflict with the outside environment if the rule names
are things like if and stat (which is a system call). Use the
-gp prefix option to prefix all functions corresponding to rules with
a string of your choice.
5. Future Work:
Predicates are still under development. We expect an enhanced
version of PCCTS that computes context and hoists more aggressively.
Often a grammar construct cannot be left factored to remove an
ambiguity. This typically arises in the situation that the common
prefix can be arbitrarily long. Fortunately, input is typically fin-
ite and one could scan past these constructs given enough lookahead.
This is not the same thing as backtracking as the parser never backs
up; it simply looks ahead really far to make a decision. This can
easily be handled with a predicate of the form:
<<is_this_found_ahead(context)>>?
which would look ahead in the lookahead buffer to see if the context
occurred within some finite number of tokens. This concept is very
similar to LR-Regular (LRR) parsers for those familiar with parsing
theory. Note that this is a very fast, cheap way to get something
resembling the power of backtracking.
Attribute names are expected to be enhanced. For example,
instead of $i, $token_name could be used:
a : WORD TYPE <<printf("%s %s\n", $WORD, $TYPE);>>
;
We expect to have a graphical user interface to PCCTS sometime in
the future which allows entry of grammars using syntax diagram nota-
tion. The interface is expected to run under X Windows.
Page 17
PCCTS
We anticipate a version that supports object-oriented programming
and generates C++ instead of ANSI C. For the moment, PCCTS is compa-
tible with C++, but future versions will support C++.
Future versions, both C and C++, will be able to refer to PCCTS
symbols by pccts.symbol instead of zzsymbol. E.g. zzskip() will
become pccts.skip().
DLG will soon use lookahead of its own to allow the recognition
of more complicated expressions; specifically, those which have left
substrings in common with other regular expressions.
We expect future versions of PCCTS to dump grammar analysis and
parser construction statistics such as how many rules required 1 token
of lookahead, how many ambiguities etc...
Page 18
